package com.shuyun.xxx.guava.algorithm;

import java.util.Scanner;

/**
 * Created by goodb on 2017/5/8.
 *
 *
 * 有一个消息队列集群，集群里每台Broker的响应时间RT都不一样，但是每台Broker的极限服务QPS都是一样的，超过这个QPS会出现过载雪崩。
 * 而消息的生产者客户端，每次发送都会选择其中的一台broker来发送，一般来说发送逻辑是运行在一个线程池里面。假设cpu资源充足，通过实现一个负载均衡算法，
 * 使得生产者能够达到最大吞吐量，最优的平均响应时间，但是又不能把任何一台服务器压垮。
 * 已知每个broker的rt、极限qps，消息生产者的线程数量，请求总数，如果采用吞吐量最优的算法，求处理完所有请求需要的耗时，单位毫秒。
 * 概念说明：
 * QPS：query per second， 每秒请求量
 * RT：response time，请求的响应时间
 * Broker：消息队列的服务器
 * 编译器版本: Java 1.8.0_66 请使用标准输入输出(System.in, System.out)；已禁用图形、文件、网络、系统相关的操作，如java.lang.Process , javax.swing.JFrame , Runtime.getRuntime；
 * 不要自定义包名称，否则会报错，即不要添加package answer之类的语句；您可以写很多个类，但是必须有一个类名为Main，并且为public属性，并且Main为唯一的public class，Main类的里面必须包含一个名字为'main'的静态方法（函数），这个方法是程序的入口
 * 时间限制: 30S (C/C++以外的语言为: 32 S)   内存限制: 200M (C/C++以外的语言为: 712 M)
 * 输入:输入数据包含5行数字: 第一行是每台broker的极限QPS 第二行是broker rt列表,用逗号分割，几个rt表示几个broker 第三行是消息生产请求总数 第四行是最大并发线程数
 * 输出:按照最大吞吐量执行完所有请求，需要耗时多少毫秒
 * 输入范例:200 1,1,1,10,10 5000 10
 * 输出范例:5000
 */
public class AliExam {
    public static void main(String[] args)  {
        Scanner in = new Scanner(System.in);
        int maxQps= Integer.valueOf(in.nextLine());
        final String[] rtList = in.nextLine().split(",");
        final int requestNum = Integer.valueOf(in.nextLine());
        final int threadNum = Integer.valueOf(in.nextLine());
        System.out.println(doneTime(maxQps, rtList, requestNum, threadNum));
    }
    /**
     * 如果使用最优的最大吞吐量负载均衡算法，按照最优模型多久能够处理完所有请求，单位毫秒。
     * @return
     */
    static long doneTime(int maxQps,String[] rtList,int requestNum,int threadNum) {
        //最终获得的总QPS
        int qpsSum = 0;
        for(String rt : rtList){
            //单个broker的QPS，单位是毫秒
            int qps = threadNum/Integer.valueOf(rt) * 1000;
            //如果单个broker的qps大于maxQps，最优选择maxQps
            if(qps > maxQps){
                qpsSum += maxQps;
            }else{
                qpsSum += qps;
            }
        }
        return requestNum/qpsSum * 1000;
    }
}



